/*
 * @lc app=leetcode.cn id=743 lang=cpp
 *
 * [743] 网络延迟时间
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        graph_.resize(n);
        k = k-1;
        for (auto& time : times) {
            int from = time[0]-1;
            int to = time[1]-1;
            int cost = time[2];

            graph_[from].emplace(to, cost);
        }

        // optimize dijkstr with priority_queue
        DP_.resize(n, 600001);

        // init just one candidate edge, one DP_dis~
        candidateQueue_.emplace(0, k);
        DP_[k] = 0;

        while (!candidateQueue_.empty()) {
            auto candidate = candidateQueue_.top();
            candidateQueue_.pop();

            int currentDis = candidate.first;
            int currentId = candidate.second;

            // >= ??? no, enven "=" may cause update
            if (currentDis > DP_[currentId]) {continue;}

            for (auto& [toId, cost] : graph_[currentId]) {
                if (DP_[toId] > DP_[currentId] + cost) {
                    DP_[toId] = DP_[currentId] + cost;
                    candidateQueue_.emplace(DP_[toId], toId);
                }
            } 
        }

        int maxCost = 0;
        for (int i=0;i<n;++i) {
            if (DP_[i] == 600001) {return -1;}
            if (DP_[i] > maxCost) {
                maxCost = DP_[i];
            }
        }
        return maxCost;
    }
private:
    //                  <to, cost>
    std::vector<std::map<int, int>> graph_;
    std::vector<int> config_;
    std::vector<int> DP_;

    // optimize
    // sorted by dis :       pair<newDisToId, Id>
    std::priority_queue<std::pair<int, int>, std::vector<pair<int,int>>, std::greater<std::pair<int, int>>> candidateQueue_;
};
// @lc code=end

int main() {
    vector<vector<int>> times = {
        {2,1,1},
        {2,3,1},
        {3,4,1}
    };
    int n=4;
    int k=2;
    Solution test;
    test.networkDelayTime(times, n, k);
}
